package algorithm.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 三数之和为0
 */
public class ThreeNumsAdd {

    /**
     * 先排序，后双指针
     * @return
     */
    private List<List<Integer>>  solve(int [] array) {
        List<List<Integer>> result = new ArrayList<>();
        if(array == null || array.length==0) {
            return result;
        }
        int len = array.length;
        Arrays.sort(array);

        for(int i=0; i<len - 2; i++) {
            //跳过相同的值
            if(i>0 && array[i] == array[i-1]) {
                continue;
            }
            int low =i+1;
            int high = len-1;
            while (low < high) {
                if(array[low] + array[high] == -array[i]) {
                    result.add(Arrays.asList(array[i], array[low], array[high]));
                    //已经找到了，去掉重复的
                    while (low < high && array[low] == array[low+1]) {
                        low++;
                    }
                    while (low < high && array[high] == array[high-1]) {
                        high--;
                    }
                    low++;
                    high--;
                } else if(array[low] + array[high] > -array[i]) {
                    high--;
                } else {
                    low++;
                }
            }
        }
        return result;
    }

    public static void main(String []args) {
        System.out.println(new ThreeNumsAdd().solve(new int []{0,0,0}));
    }
}
